package com.leetcode.No1600;

import org.junit.Test;

import java.util.*;

/**
 * @program: leetcode
 * @description: 皇位继承顺序
 * @author: wangzhihua
 * @date: 2021-06-21
 */
public class ThroneInheritance {

	private String king;
	// key = 本人Name, value = 本人信息
	private HashMap<String, HeirInfo> heirMap = new HashMap<String, HeirInfo>();
	// 通过孩子快速找到父亲，key = sonName, value = fatherName
	private HashMap<String, String> sonFatherMap = new HashMap<String, String>();

	public ThroneInheritance(String kingName) {
		king = kingName;
		heirMap.put(king, new HeirInfo());
		sonFatherMap.put(king, null);
	}

	public void birth(String parentName, String childName) {
		sonFatherMap.put(childName, parentName);

		heirMap.get(parentName).offsprings.add(childName);

		heirMap.put(childName, new HeirInfo());
	}

	public void death(String name) {
		heirMap.get(name).isAlive = false;
	}

	public List<String> getInheritanceOrder() {
		return findHeir(king, new ArrayList<String>());
	}

	private List<String> findHeir(String father, List<String> heirs) {
		if (heirMap.get(father).isAlive) {
			heirs.add(father);
		}
		for (String heir : heirMap.get(father).offsprings) {
			findHeir(heir, heirs);
		}
		return heirs;
	}

	private class HeirInfo {
		public boolean isAlive = true;
		public ArrayList<String> offsprings = new ArrayList<String>();
	}

}
